package com.sanyue.dataStructure.Sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author sanyue
 * @version 1.0
 * @description: TODO
 * @date 2022/2/25 下午12:49
 */
public class Quick {
    @Test
    public void fun1(){
        int[] arr = new int[]{-1,2,3,1,2,4,6,5,7,8,9};

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println("");

        quickSort2(arr,0,arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    public void quickSort2(int[] arr, int low, int high){
        if (low >= high) return;
        int i = low, j = high, Base = arr[low];
        while (i < j){
            while (arr[j] >= Base && i < j) j--;
            while (arr[i] <= Base && i < j) i++;
            swap2(arr, i, j);
        }
        swap2(arr, low , j);
        quickSort2(arr, low, j-1);
        quickSort2(arr, j+1, high);

    }
    void swap2(int arr[], int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    void quickSorts(int[] arr,int low,int high){
        if (low >= high) return;
        int i = low, j = high, Base = arr[low];
        while (i < j){
            while (arr[j] >= Base && i < j) j--;
            while (arr[i] <= Base && i < j) i++;
            swap(arr, i, j);
        }
        swap(arr, low , j);
        quickSorts(arr, low, j-1);
        quickSorts(arr, j+1, high);
    }




    public void quickSort(int[] arr, int low, int high) {
        // low,high 为每次处理数组时的首、尾元素索引

        //当low==high是表示该序列只有一个元素，不必排序了
        if (low >= high) {
            return;
        }
        // 选出哨兵元素和基准元素。这里左边的哨兵元素也是基准元素
        int i = low, j = high, base = arr[low];
        while (i < j) {
            //右边哨兵从后向前找
            while (arr[j] >= base && i < j) {
                j--;
            }
            //左边哨兵从前向后找
            while (arr[i] <= base && i < j) {
                i++;
            }
            swap(arr,i,j);  //交换元素
        }
        swap(arr,low,j);  //基准元素与右哨兵交换

        //递归调用，排序左子集合和右子集合
        quickSort(arr,low,j-1);
        quickSort(arr,j+1,high);

    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}
